软考真题
第40题
最大尺寸和问题描述为,在n个整数(包含负数)的 数组 A中,求之和最大的非空连续子 数组 ,如 数组 A=(-2,11,-4,13,-5,-2) ,其中子 数组 B=(11,-4,13)具有最大子段和20(11-4+13=20) 。求解该问题时,可以将 数组 分为两个n/2个整数的子 数组 最大子段或或者在前半段,或者在后半段,或者跨越中间元素,通过该方法继续划分问题,直至最后求出最大子段和,该算法的时间复杂度为( )